#include <cstddef>
#include <queue>
#include <vector>
using namespace std;
class Node {
public:
  int val;
  Node *left;
  Node *right;
  Node *next;

  Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}

  Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}

  Node(int _val, Node *_left, Node *_right, Node *_next)
      : val(_val), left(_left), right(_right), next(_next) {}
};

Node *connect(Node *root) {
  if (root == nullptr) {
    return nullptr;
  }
  queue<Node *> q;
  q.push(root);
  while (!q.empty()) {
    int n = q.size();
    Node *last_node = nullptr;
    while (n--) {
      Node *node = q.front();
      q.pop();
      if (node->left)
        q.push(node->left);
      if (node->right)
        q.push(node->right);
      if (last_node != nullptr) {
        last_node->next = node;
      }
      last_node = node;
    }
  }
  return root;
}
